<?php
/**
 * @title 399. 除法求值 - 穷列
 * @author start2004
 */

// ini_set("memory_limit", "128M");


class Solution {

    /**
     * @param String[][] $equations
     * @param Float[] $values
     * @param String[][] $queries
     * @return Float[]
     */
    function calcEquation($equations, $values, $queries) {
        /**
         * @since 2020-08-14 哈希存储除法结果
         */
        $hashs = [];

        /**
         * @since 2020-08-14 长度
         */
        $len = count($equations);

        /**
         * @since 2020-08-14 变量
         */
        $variables = [];

        /**
         * @since 2020-08-14 遍历方程式
         */
        for ($i=0; $i<$len; $i++){
            list($a, $b) = $equations[$i];
            $val = $values[$i];

            $hashs[$a][$b] = $val;
            $hashs[$b][$a] = 1/$val;
            $hashs[$a][$a] = 1.0;
            $hashs[$b][$b] = 1.0;
        }

        /**
         * @since 2020-08-14 穷列
         */
        foreach ($hashs as $keyA=>$nexts){
            // echo "keyA={$keyA}, next=[", implode(", ", array_keys($nexts)), "]", PHP_EOL;
            while($nexts){
                $nextsTmp = [];

                /**
                 * @since 2020-08-14 a/b, b/c, 推到 a/c
                 */
                foreach ($nexts as $keyB=>$valB){
                    foreach ($hashs[$keyB] as $keyC=>$valC){
                        if(!isset($hashs[$keyA][$keyC])){
                            // echo "new {$keyA}/{$keyC}", PHP_EOL;
                            $val = $valB*$valC;
                            $hashs[$keyA][$keyC] = $val;
                            $hashs[$keyC][$keyA] = 1/$val;
                            $nextsTmp[$keyC] = $val;
                        } else {}
                    }
                }

                /**
                 * @since 2020-08-14 下次迭代
                 */
                $nexts = $nextsTmp;
            }

        }

        /**
         * @since 2020-08-14 问题方程式结果集
         */
        $result = [];

        /**
         * @since 2020-08-14 问题方程式
         */
        for ($i=0, $qLen=count($queries); $i<$qLen; $i++){
            list($a, $b) = $queries[$i];
            
            if(isset($hashs[$a][$b])){
                $result[] = $hashs[$a][$b];
            } else {
                $result[] = -1.0;
            }
        }

        /**
         * @return
         */
        return $result;
    }
}


/**
 * @url http://127.0.0.1/leetcode/202008/2020.08.14_2.php
 */
$datas = [
    [
        [["a","b"],["b","c"]],
        [2.0, 3.0],
        [["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"]],
    ]
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->calcEquation($data[0], $data[1], $data[2]);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
